package pers.qianyu.month_202012.date_20201225.dp_bag;

import pers.qianyu.util.*;

/**
 * 125. 背包问题 II
 * https://www.lintcode.com/problem/backpack-ii/description
 * <strong>01背包最值问题，背包价值和重量不相同的情况</strong>
 *
 * @author mizzle rain
 * @date 2020-12-25 14:44
 */
public class BackPackII {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            int size = A[i];
            int value = V[i];
            for (int j = m; j > 0; j--) {
                if (j >= size) {
                    dp[j] = Math.max(dp[j], dp[j - size] + value);
                }
            }
            ArrayUtil.printArrayAsMarkdownTable(String.format("size:%s value:%s", size, value), dp);
        }
        return dp[m];
    }

    public static void main(String[] args) {
        int m = 10;
        int[] A = {2, 3, 5, 7};
        int[] V = {1, 5, 2, 4};
        int result = new BackPackII().backPackII(m, A, V);
        System.out.println("result = " + result);
    }
}
